package cn.aylog.algorithm;

import java.util.Arrays;

/**
 * 希尔排序
 *  对插入排序的一个优化
 */
public class ShellSort {
    public static void main(String[] args) {
        // int arr[] = {8,9,1,7,2,3,5,4,6};
        // shellSort(arr);
        // Arrays.stream(arr).forEach(i -> System.out.printf("%d ", i));
        int len = 800000;
        int[] arr = new int[len];
        for(int i=0; i<len; i++) {
            arr[i] = (int)(Math.random()*8000000);
        }
        long start = System.currentTimeMillis();
        shellSort(arr); //  152 162 162
        long end = System.currentTimeMillis();
        System.out.println("insertSort耗时: " + (end - start));
    }

    public static void shellSort(int arr[]) {
        int len = arr.length;
        int step = len;
        int insertValue, index;
        while(step > 1) {
            step = (int) Math.floor(step/2);
            // 分组
            for(int x=0; x<step; x++) {
                // 对各分组进行插入排序
                for(int y=x; y<len; y += step) {
                    insertValue = arr[y];
                    index = y - step;
                    while(index >= 0 && insertValue < arr[index]) {
                        arr[index + step] = arr[index];
                        index -= step;
                    }
                    arr[index+step] = insertValue;
                }
            }
        }
    }
}
